The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Modern network elements that forward packets in packet-switched networks typically separate their forwarding services (e.g. the tasks of moving packets from one network interface to another) from their routing services (e.g. the tasks of determining the best path through the network). For example, a network element, such as a router, typically receives a packet at one of its network interfaces and forwards the packet to another of its network interfaces. In making the decision to which network interface to forward the packet, the network element typically uses information included in the header of the packet, as well as routing information stored and managed by the network element.
The routing information managed by a network element comprises information about the connectivity between the nodes of the network in which the network element is established, and information about the connectivity to nodes in other networks.
For example, the routing information may include the routes to the network destinations that are reachable from the network element. A route comprises an address destination, which is usually represented by an address prefix (also referred to as prefix), and information that describe the path to the address destination. The address prefix may be expressed as a combination of a network address and a mask that indicates how many bits of the address are used to identify the network portion of the address. The information that describes the path to the address destination may include, for example, the address of a node that is the next hop to the address destination, the list of Autonomous Systems (ASs) that must be traversed in order to reach the address destination, and the network address of the node that originated the route.
The routing information managed by a network element may also include information that indicates the type of each network interface of the network element, the network node or nodes that are connected to the network element over each network interface, and various other parameters that may be associated with the network element or its network interfaces.
A network element that separates its forwarding service from its routing service typically stores all of its routing information in a Routing Information Base (RIB). Each routing protocol that executes on the network element selects its own set of best routes, and installs those routes and their attributes in the RIB. Within a routing protocol, the routes are selected based on one or more criteria, or metrics, used by that protocol. A RIB process periodically traverses the routes in the RIB and selects the best overall route to each address destination by comparing the attributes of all routes to that destination. The routes identified in the RIB as best routes are then transferred, or downloaded, to one or more Forwarding Information Bases (FIBs) that are used for forwarding packets by the one or more network interfaces of the network element. Thus, at any given point in time a FIB maintains an image of all or a subset of the routing information contained in the RIB. When routing or topology changes occur in the network, the routing information in the RIB is updated and the changes to the routing information are reflected in the one or more FIBs.
Network elements may store the routing information in the RIB as one or more logically or physically separate routing tables to facilitate orderly management of different services. For example, a network element that supports Virtual Private Network (VPN) features usually manages the routes of different VPNs in separate logical or physical routing tables. In another example, a network element may manage routes for different topologies, such as, for example, topologies associated with a different Quality of Service (QoS), in separate routing tables. Further, a plurality of network elements may execute as a virtual router, and each network element in the virtual router may store the RIBs of the other network elements of the virtual router in logically or physically separate routing tables.
The order of transferring data from a RIB to a FIB may affect the availability of services. Even though the routes in the RIB may be managed in separate routing tables, since the network element does not have the capability to treat these separate routing tables differently, the network element has no way to determine which routing tables should be downloaded first to the FIB when a routing or a topology change occurs.
For example, suppose that a network element is established on the edge of an Internet Service Provider (ISP) network. Further, suppose that the ISP provides a VPN connectivity for one of its customers, and that the network element stores the routes of the VPN in a separate VPN Route Forwarding (VRF) routing table of its RIB. Suppose also that a routing or a topology change causes changes to both the routes in the VRF table and the routes in the network element's large Internet routing table. In order to ensure uninterrupted forwarding service, the network element must download these changes as fast as possible from the RIB to the FIBs of its network interfaces. However, since the network element does not have the ability to distinguish priority among the routes nor any routing tables of its RIB, the network element may download the routes from its large Internet routing table before it downloads to the FIBs the routes from the VRF routing table. Thus, the forwarding service on Internet routes will be restored before the forwarding service on the customer's VPN routes even though the VPN customer may have been promised premium service.
This inability of the network element to determine which routing information should be first downloaded to the FIB may also cause interruption of forwarding service on individual routes. Suppose that a routing protocol installs in the RIB a new address prefix for a destination for which an interrupted forwarding service is guaranteed. Since the network element is unable to determine the importance of the new address prefix with respect to forwarding, the network element will treat the new address prefix as a normal prefix and will continue with downloading other address prefixes first. As a result, the new address prefix may not be downloaded to the FIB for a while, and in the meantime the forwarding service to the destination is interrupted.
Based on the foregoing, there is a clear need for a technique for improved processing of routing information at network elements.